package developer.算法.二叉树.二叉树最近的公共祖先;

import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

/**
 * @author zhangyongkang
 * @time 2025/3/27 20:34
 * @description 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
public class ErChaShuZuiJinDeGongGongZuXian {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode treeNode = new TreeNode(3, new TreeNode(5, new TreeNode(6), new TreeNode(2, new TreeNode(7), new TreeNode(4))), new TreeNode(1, new TreeNode(0), new TreeNode(8)));
        TreeNode result = solution.lowestCommonAncestor(treeNode, new TreeNode(5), new TreeNode(1));
        TreeNode result1 = solution.lowestCommonAncestor(treeNode, new TreeNode(5), new TreeNode(4));
        System.out.println(result);
    }

    static class Solution4 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return null;
            if (root == p) {
                return p;
            }
            if (root == q) {
                return q;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            return left == null ? right : right == null ? root : null;
        }
    }


    static class Solution3 {

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return null;
            if (root == p) {
                return p;
            }
            if (root == q) {
                return q;
            }
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            return l == null ? r : r == null ? root : r;
        }
    }

    static class Solution {
        Map<Integer, TreeNode> map = new HashMap<>();


        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            //判定当前节点是否为两个目标节点的祖先
            //获取当前节点的深度 取最大深度的数
            baseTree(root, p, q, 0);
            Optional<Integer> max = map.keySet().stream().max(Integer::compareTo);
            return max.map(integer -> map.get(integer)).orElse(null);
        }

        public void baseTree(TreeNode root, TreeNode p, TreeNode q, int level) {
            if (root == null) return;
            boolean pF = findNode(root, p, false);
            boolean qF = findNode(root, q, false);
            if (pF && qF) {
                map.put(level, root);
            }
            baseTree(root.left, p, q, level++);
            baseTree(root.right, p, q, level++);
        }

        public boolean findNode(TreeNode root, TreeNode target, boolean flag) {
            if (root == null) return flag;
            if (root.val == target.val) {
                return true;
            }
            boolean r1 = findNode(root.left, target, flag);
            boolean r2 = findNode(root.right, target, flag);
            return r1 || r2;
        }
    }

    static class SolutionOther {

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) {
                return root;
            }
            TreeNode l = lowestCommonAncestor(root.left, p, q);
            TreeNode r = lowestCommonAncestor(root.right, p, q);
            //如果 l 是null  那么r节点就包含了 pq
            //如果 r 是null  那么l节点包含了 pq
            //如果都不是null  那么当前节点就是祖先
            return l == null ? r : r == null ? l : root;
        }

    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
